#!/usr/bin/env python
from random import randrange as RANDOM
def split(A,low,high):
	priov = A[low]
	i     = low
	for j in range(low+1,high+1):
		if A[j] <= priov :
			i = i + 1
			if i != j :
				A[i],A[j] = A[j],A[i]
	A[low],A[i] = A[i],A[low]
	return i

def random_split(A,low,high):
	i = RANDOM(low,high+1)
	A[i],A[low] = A[low],A[i]
	return split(A,low,high)

def quicksort(A,low,high):
	if low < high :
		w = random_split(A,low,high)
		quicksort(A,low,w-1)
		quicksort(A,w+1,high)

if __name__ == '__main__':
	A = [1,5,3,9,2]
	low = 0
	high = len(A)-1
	print 'before quicksort,the sequence is %s'% A
	quicksort(A,low,high)
	print 'after quicksort ,the sequence is %s' % A
